#ifndef TIM_HASHTABLE_H
#define TIM_HASHTABLE_H
#include "tim_vector.h"
#include "tim_string.h"

namespace tim
{
	template<typename K, typename V>
	class entry//词条类
	{
		public:
			K key;
			V value;
			entry(K k = K(), V v = V()): key(k), value(v) {};
			bool operator<(tim::entry<K, V> e) {return key < e.key; };
			bool operator>(tim::entry<K, V> e) {return key > e.key; };
			bool operator==(tim::entry<K, V> e) {return key == e.key; };
			bool operator!=(tim::entry<K, V> e) {return  key != e.key; };
	};

	#define M 13

	template<typename K, typename V>
	class hashtable//基于除余法、开放定址法的哈希表
	{
		private:
			entry<K, V>** ht;//桶
			bool* lazy_mark;
			int _capcity;
			int _size;
			int probe4hit(K const& k);//试探存在词条
			int probe4free(K const& k);//试探不存在词条
			int hash(char key[]);//哈希函数, 除余, 以下为重载, 对字符串哈希
			int hash(int key) {return key % _capcity;};//对32位以内的哈希，下同
			int hash(char key) {return hash((int)key);}
			int hash(long long key) {return hash(std::to_string(key).c_str());}//转为字符串哈希，下同
			int hash(double key) {return hash(std::to_string(key).c_str());}
			int hash(float key) {return hash(std::to_string(key).c_str());}
			int hash(std::string key) {return hash(key.c_str());};
			int hash(tim::string key) {return hash(key.c_str());};
			void rehash();//重哈希

		public:
			hashtable(int m = M);
			bool put(K const& k, V const& v);//装入词条
			V& get(K const& k) { return ht[probe4hit(k)]->value; };//获得值
			V remove(K const& k);//删除词条
	};
}

#include "tim_string.h"
#include<typeinfo>

template<typename K, typename V>
tim::hashtable<K, V>::hashtable(int m)
{
	ht = new tim::entry<K, V>*[m];
	lazy_mark = new bool[m];
	for (int i = 0; i < m; i++) lazy_mark[i] = false;
	_size = 0;
	_capcity = m;
}

template<typename K, typename V>
int tim::hashtable<K, V>::hash(char c[])
{
	int temp = 0;
	int n = strlen(c);

	for (int i = 0; i < n; i++) {
		temp = (temp << 5) | (temp >> 27);
		temp += (int)c[i];
	}

	return temp % _capcity;
}

template<typename K, typename V>
int tim::hashtable<K, V>::probe4free(const K &k)
{
	int r = hash(k);
	while (ht[r]) r += 1;
	return r;
}

template<typename K, typename V>
int tim::hashtable<K, V>::probe4hit(K const& k)
{
	int r = hash(k);
	while ( (ht[r] && (k != ht[r]->key)) || (!ht[r] && lazy_mark[r])) r += 1;
	return r;
}

template<typename K, typename V>
bool tim::hashtable<K, V>::put(K const& k, V const& v)
{
	if (ht[probe4hit(k)]) return false;
	int r = probe4free(k);
	ht[r] = new tim::entry<K, V>(k, v);
	_size++;
	lazy_mark[r] = true;
	if (_size * 2 > _capcity) rehash();
	return true;
}

template<typename K, typename V>
V tim::hashtable<K, V>::remove(K const& k)
{
	int r = probe4hit(k);
	if (!ht[r]) return V();
	V temp = ht[r]->value;
	delete ht[r];
	ht[r] = nullptr;
	return temp;
}

template<typename K, typename V>
void tim::hashtable<K, V>::rehash()
{
	_capcity *= 2;
	tim::entry<K, V>** new_ht = new tim::entry<K, V>*[_capcity];
	delete lazy_mark;

	lazy_mark = new bool[_capcity];
	for (int i = 0; i < _capcity; i++) lazy_mark[i] = false;

	for (int i = 0; i < _capcity / 2; i++)
		if (ht[i]) {
			new_ht[i] = new tim::entry<K, V>(ht[i]->key, ht[i]->value);
			lazy_mark[i] = true;
		}

	delete ht;
	ht = new_ht;
}

#endif
